Правильно: советское правительство. Слово советский пишется со строчной буквы (но: Советская армия, Советская страна, Советский Союз, Советское информбюро).
Правильно: Советская армия.
Корректно: Советская армия, Российская армия.
В советское время этот праздник назывался День Советской Армии и Военно-Морского Флота. См.: Прописная или строчная? Словарь-справочник (М., 1989). Современное название – День защитника Отечества. См.: Лопатин В. В., Нечаева И. В., Чельцова Л. К. Прописная или строчная? Орфографический словарь. М., 2011.